package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/3sum/">三数之和(3Sum)</a>
 * <p>给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
 * <p>请你返回所有和为 0 且不重复的三元组。</p>
 * <p>注意：答案中不可以包含重复的三元组。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [-1,0,1,2,-1,-4]
 *      输出：[[-1,-1,2],[-1,0,1]]
 *      解释：
 *          nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 *          nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 *          nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 *      不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 *      注意，输出的顺序和三元组的顺序并不重要。
 *
 * 示例 2：
 *      输入：nums = [0,1,1]
 *      输出：[]
 *      解释：唯一可能的三元组和不为 0 。
 *
 * 示例 3：
 *      输入：nums = [0,0,0]
 *      输出：[[0,0,0]]
 *      解释：唯一可能的三元组和为 0
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>3 <= nums.length <= 3000</li>
 *      <li>-10^5 <= nums[i] <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/5 10:15
 */
public class LC0015ThreeSum_M {

    static class Solution {

        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> resultList = new ArrayList<>();
            // 如果所有的值都大于0或者所有的值都小于0
            if (nums[0] > 0 || nums[nums.length - 1] < 0) {
                return resultList;
            }
            for (int first = 0; first <= nums.length - 3; first++) {
                // 外层去重，避免相同的数字被计算两次
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }
                int target = -nums[first];
                int second = first + 1;
                int third = nums.length - 1;
                while (second < third) {
                    if (nums[second] + nums[third] > target) {
                        --third;
                    } else if (nums[second] + nums[third] < target) {
                        ++second;
                    } else {
                        resultList.add(Arrays.asList(nums[first], nums[second++], nums[third--]));

                        // 内层去重：避免出现相同的结果。例如：-1 0 0 1 1 ==>结果中应该只出现一组[-1,0,0]
                        while (second < third && nums[second] == nums[second - 1]) {
                            ++second;
                        }
                        while (second < third && nums[third] == nums[third + 1]) {
                            --third;
                        }
                    }
                }
            }
            return resultList;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        Printer.printListListInteger(solution.threeSum(new int[]{0, 1, 1}));
        Printer.printListListInteger(solution.threeSum(new int[]{0, 0, 0}));
    }
}